/*
 * @Author: 缄默
 * @Date: 2021-11-09 21:45:03
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 19:14:51
 */

//找到二叉树中的最大搜索二叉树


#include <iostream>
#include <vector>
#include <map>
#include "../../DataStructure/tree.hpp"

using namespace std;

struct returnType {
    TreeNode* Node;
    int NodeNum;
    int max;
    int min;
    returnType(TreeNode* Node1, int x1, int x2, int x3) : Node(Node1), NodeNum(x1), max(x2), min(x3) { }
};

returnType* process(TreeNode* node) ;

int main() {
    vector<int> preOrder({4, 2, 1, 3, 6, 5, 7});
    vector<int> inOrder({1, 2, 3, 4, 5, 6, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    returnType* data = process(head);
    cout << data->Node->val;
    return 0;
}

returnType* process(TreeNode* node) {
    if (node == nullptr) return new returnType(nullptr, 0, 0, 0);
    returnType* lData = process(node->left);
    returnType* rData = process(node->right);
    if (lData->Node == node->left && rData->Node == node->right) {
        if (lData->max < node->val && (node->val < rData->min || rData->min == 0)) {
            int NodeNum = lData->NodeNum + 1 + rData->NodeNum;
            int max = rData->max > node->val ? rData->max : node->val;
            int min = lData->min == 0 ? node->val : lData->min;
            return new returnType(node, NodeNum, max, min);
        }
    } 
    return lData->NodeNum > rData->NodeNum ? lData : rData;
    
}